/*
 * Copyright (C) 2011 Nicola Bonzanni
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package nl.vu.few.ibivu.jlemon.algorithms;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Map;

import nl.vu.few.ibivu.jlemon.NodeIterator;
import nl.vu.few.ibivu.jlemon.NodeMap;
import nl.vu.few.ibivu.jlemon.OutgoingArcIterator;
import nl.vu.few.ibivu.jlemon.PredMapPath;
import nl.vu.few.ibivu.jlemon.concepts.Arc;
import nl.vu.few.ibivu.jlemon.concepts.Graph;
import nl.vu.few.ibivu.jlemon.concepts.Node;
import nl.vu.few.ibivu.jlemon.concepts.Path;
import nl.vu.few.ibivu.jlemon.utils.BooleanContainer;
import nl.vu.few.ibivu.jlemon.utils.ObjectContainer;

public class Bfs<N extends Node & Comparable<N>, A extends Arc & Comparable<A>> {
	// Pointer to the underlying graph.
	Graph<N, A> graph;
	// Pointer to the map of predecessor arcs.
	Map<N, A> pred;
	Map<N, A> predExternal;
	// Pointer to the map of distances.
	Map<N, Integer> dist;
	Map<N, Integer> distExternal;
	// Pointer to the map of reached status of the nodes.
	Map<N, Boolean> reached;
	
	// Pointer to the map of processed status of the nodes.
	// NB: apparently never used!
	// NodeMap<N, Boolean> _processed;
	
	ArrayList<N> queue;
	int queueHead, queueTail, queueNextDist;
	int currDist;
	
	public Bfs(Graph<N, A> graph) {
		super();
		this.graph = graph;
	}

	public Bfs(Graph<N, A> graph, Map<N, A> pred, Map<N, Integer> dist) {
		this(graph);
		this.predExternal = pred;
		this.distExternal = dist;
	}

	public void init() {
		pred = (predExternal == null) ? new NodeMap<N, A>(graph, null) : predExternal;
		dist = (distExternal == null) ? new NodeMap<N, Integer>(graph, 0) : distExternal;
		reached = new NodeMap<N, Boolean>(graph, false);
		// _processed = new NodeMap<N, Boolean>(graph, false);
		queue = new ArrayList<N>(Collections.nCopies(graph.nodeNum(), (N) null));
		queueHead = queueTail = 0;
	}

	// /Adds a new source node.

	// /Adds a new source node to the set of nodes to be processed.
	// /
	void addSource(N s) {
		if (!(reached.get(s))) {
			reached.put(s, true);
			pred.put(s, null);
			dist.put(s, 0);
			queue.set(queueHead++, s);
			queueNextDist = queueHead;
		}
	}

	// /Processes the next node.

	// /Processes the next node.
	// /
	// /\return The processed node.
	// /
	// /\pre The queue must not be empty.
	Node processNextNode() {
		if (queueTail == queueNextDist) {
			currDist++;
			queueNextDist = queueHead;
		}
		N n = queue.get(queueTail++);
		// _processed.put(n, true);
		N m;
		for (OutgoingArcIterator<A> e = new OutgoingArcIterator<A>(graph, n); e.hasNext();) {
			e.next();
			if (!reached.get(m = graph.target(e.peek()))) {
				queue.set(queueHead++, m);
				reached.put(m, true);
				pred.put(m, e.peek());
				dist.put(m, currDist);
			}
		}
		return n;
	}

	// /Processes the next node.

	// /Processes the next node and checks if the given target node
	// /is reached. If the target node is reachable from the processed
	// /node, then the \c reach parameter will be set to \c true.
	// /
	// /\param target The target node.
	// /\retval reach Indicates if the target node is reached.
	// /It should be initially \c false.
	// /
	// /\return The processed node.
	// /
	// /\pre The queue must not be empty.
	N processNextNode(N target, BooleanContainer reach) {
		if (queueTail == queueNextDist) {
			currDist++;
			queueNextDist = queueHead;
		}
		N n = queue.get(queueTail++);
		// _processed.put(n, true);
		N m;
		for (OutgoingArcIterator<A> e = new OutgoingArcIterator<A>(graph, n); e.hasNext();) {
			e.next();
			if (!reached.get(m = graph.target(e.peek()))) {
				queue.set(queueHead++, m);
				reached.put(m, true);
				pred.put(m, e.peek());
				dist.put(m, currDist);
				reach.value = reach.value || (target.equals(m));
			}
		}
		return n;
	}

	// /Processes the next node.

	// /Processes the next node and checks if at least one of reached
	// /nodes has \c true value in the \c nm node map. If one node
	// /with \c true value is reachable from the processed node, then the
	// /\c rnode parameter will be set to the first of such nodes.
	// /
	// /\param nm A \c bool (or convertible) node map that indicates the
	// /possible targets.
	// /\retval rnode The reached target node.
	// /It should be initially \c INVALID.
	// /
	// /\return The processed node.
	// /
	// /\pre The queue must not be empty.
	N processNextNode(Map<N, Boolean> nm, ObjectContainer<N> rnode) {
		if (queueTail == queueNextDist) {
			currDist++;
			queueNextDist = queueHead;
		}
		N n = queue.get(queueTail++);
		// _processed.put(n, true);
		N m;
		for (OutgoingArcIterator<A> e = new OutgoingArcIterator<A>(graph, n); e.hasNext();) {
			e.next();
			if (!reached.get(m = graph.target(e.peek()))) {
				queue.set(queueHead++, m);
				reached.put(m, true);
				pred.put(m, e.peek());
				dist.put(m, currDist);
				if (nm.get(m) && rnode.value == null)
					rnode.value = m;
			}
		}
		return n;
	}

	// /The next node to be processed.

	// /Returns the next node to be processed or \c INVALID if the queue
	// /is empty.
	N nextNode() {
		return queueTail < queueHead ? queue.get(queueTail) : null;
	}

	// /Returns \c false if there are nodes to be processed.

	// /Returns \c false if there are nodes to be processed
	// /in the queue.
	boolean emptyQueue() {
		return queueTail == queueHead;
	}

	// /Returns the number of the nodes to be processed.

	// /Returns the number of the nodes to be processed
	// /in the queue.
	int queueSize() {
		return queueHead - queueTail;
	}

	// /Executes the algorithm.
	// /
	// /This method runs the %BFS algorithm from the root node(s)
	// /in order to compute the shortest path to each node.
	// /
	// /The algorithm computes
	// /- the shortest path tree (forest),
	// /- the distance of each node from the root(s).
	// /
	// /\pre init() must be called and at least one root node should be
	// /added with addSource() before using this function.
	// /
	// /\note <tt>b.start()</tt> is just a shortcut of the following code.
	// /\code
	// / while ( !b.emptyQueue() ) {
	// / b.processNextNode();
	// / }
	// /\endcode
	void start() {
		while (!emptyQueue())
			processNextNode();
	}

	// /Executes the algorithm until the given target node is reached.

	// /Executes the algorithm until the given target node is reached.
	// /
	// /This method runs the %BFS algorithm from the root node(s)
	// /in order to compute the shortest path to \c t.
	// /
	// /The algorithm computes
	// /- the shortest path to \c t,
	// /- the distance of \c t from the root(s).
	// /
	// /\pre init() must be called and at least one root node should be
	// /added with addSource() before using this function.
	// /
	// /\note <tt>b.start(t)</tt> is just a shortcut of the following code.
	// /\code
	// / bool reach = false;
	// / while ( !b.emptyQueue() && !reach ) {
	// / b.processNextNode(t, reach);
	// / }
	// /\endcode
	void start(N t) {
		BooleanContainer reach = new BooleanContainer(false);
		while (!emptyQueue() && !reach.value)
			processNextNode(t, reach);
	}

	// /Executes the algorithm until a condition is met.

	// /Executes the algorithm until a condition is met.
	// /
	// /This method runs the %BFS algorithm from the root node(s) in
	// /order to compute the shortest path to a node \c v with
	// / <tt>nm[v]</tt> true, if such a node can be found.
	// /
	// /\param nm A \c bool (or convertible) node map. The algorithm
	// /will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
	// /
	// /\return The reached node \c v with <tt>nm[v]</tt> true or
	// /\c INVALID if no such node was found.
	// /
	// /\pre init() must be called and at least one root node should be
	// /added with addSource() before using this function.
	// /
	// /\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
	// /\code
	// / Node rnode = INVALID;
	// / while ( !b.emptyQueue() && rnode == INVALID ) {
	// / b.processNextNode(nm, rnode);
	// / }
	// / return rnode;
	// /\endcode
	N start(Map<N, Boolean> nm) {
		ObjectContainer<N> rnode = new ObjectContainer<N>(null);
		while (!emptyQueue() && rnode.value == null) {
			processNextNode(nm, rnode);
		}
		return rnode.value;
	}

	// /Runs the algorithm from the given source node.

	// /This method runs the %BFS algorithm from node \c s
	// /in order to compute the shortest path to each node.
	// /
	// /The algorithm computes
	// /- the shortest path tree,
	// /- the distance of each node from the root.
	// /
	// /\note <tt>b.run(s)</tt> is just a shortcut of the following code.
	// /\code
	// / b.init();
	// / b.addSource(s);
	// / b.start();
	// /\endcode
	void run(N s) {
		init();
		addSource(s);
		start();
	}

	// /Finds the shortest path between \c s and \c t.

	// /This method runs the %BFS algorithm from node \c s
	// /in order to compute the shortest path to node \c t
	// /(it stops searching when \c t is processed).
	// /
	// /\return \c true if \c t is reachable form \c s.
	// /
	// /\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
	// /shortcut of the following code.
	// /\code
	// / b.init();
	// / b.addSource(s);
	// / b.start(t);
	// /\endcode
	boolean run(N s, N t) {
		init();
		addSource(s);
		start(t);
		return reached(t);
	}

	// /Runs the algorithm to visit all nodes in the digraph.

	// /This method runs the %BFS algorithm in order to
	// /compute the shortest path to each node.
	// /
	// /The algorithm computes
	// /- the shortest path tree (forest),
	// /- the distance of each node from the root(s).
	// /
	// /\note <tt>b.run(s)</tt> is just a shortcut of the following code.
	// /\code
	// / b.init();
	// / for (NodeIt n(gr); n != INVALID; ++n) {
	// / if (!b.reached(n)) {
	// / b.addSource(n);
	// / b.start();
	// / }
	// / }
	// /\endcode
	void run() {
		init();
		for (NodeIterator<N> n = new NodeIterator<N>(graph); n.hasNext();) {
			n.next();
			if (!reached(n.peek())) {
				addSource(n.peek());
				start();
			}
		}
	}

	// /\name Query Functions
	// /The results of the BFS algorithm can be obtained using these
	// /functions.\n
	// /Either \ref run(Node) "run()" or \ref start() should be called
	// /before using them.

	// /@{

	// /The shortest path to a node.

	// /Returns the shortest path to a node.
	// /
	// /\warning \c t should be reached from the root(s).
	// /
	// /\pre Either \ref run(Node) "run()" or \ref init()
	// /must be called before using this function.
	Path<A> path(N t) {
		return new PredMapPath<N, A>(graph, pred, t);
	}

	// /The distance of a node from the root(s).

	// /Returns the distance of a node from the root(s).
	// /
	// /\warning If node \c v is not reached from the root(s), then
	// /the return value of this function is undefined.
	// /
	// /\pre Either \ref run(Node) "run()" or \ref init()
	// /must be called before using this function.
	int dist(N v) {
		return dist.get(v);
	}

	// /Returns the 'previous arc' of the shortest path tree for a node.

	// /This function returns the 'previous arc' of the shortest path
	// /tree for the node \c v, i.e. it returns the last arc of a
	// /shortest path from a root to \c v. It is \c INVALID if \c v
	// /is not reached from the root(s) or if \c v is a root.
	// /
	// /The shortest path tree used here is equal to the shortest path
	// /tree used in \ref predNode().
	// /
	// /\pre Either \ref run(Node) "run()" or \ref init()
	// /must be called before using this function.
	A predArc(N v) {
		return pred.get(v);
	}

	// /Returns the 'previous node' of the shortest path tree for a node.

	// /This function returns the 'previous node' of the shortest path
	// /tree for the node \c v, i.e. it returns the last but one node
	// /from a shortest path from a root to \c v. It is \c INVALID
	// /if \c v is not reached from the root(s) or if \c v is a root.
	// /
	// /The shortest path tree used here is equal to the shortest path
	// /tree used in \ref predArc().
	// /
	// /\pre Either \ref run(Node) "run()" or \ref init()
	// /must be called before using this function.
	N predNode(N v) {
		return pred.get(v) == null ? null : graph.source(pred.get(v));
	}

	// /\brief Returns a const reference to the node map that stores the
	// / distances of the nodes.
	// /
	// /Returns a const reference to the node map that stores the distances
	// /of the nodes calculated by the algorithm.
	// /
	// /\pre Either \ref run(Node) "run()" or \ref init()
	// /must be called before using this function.
	Map<N, Integer> distMap() {
		return dist;
	}

	// /\brief Returns a const reference to the node map that stores the
	// /predecessor arcs.
	// /
	// /Returns a const reference to the node map that stores the predecessor
	// /arcs, which form the shortest path tree.
	// /
	// /\pre Either \ref run(Node) "run()" or \ref init()
	// /must be called before using this function.
	Map<N, A> predMap() {
		return pred;
	}

	// /Checks if a node is reached from the root(s).

	// /Returns \c true if \c v is reached from the root(s).
	// /
	// /\pre Either \ref run(Node) "run()" or \ref init()
	// /must be called before using this function.
	boolean reached(N v) {
		return reached.get(v);
	}
	
	public void setPredMap(Map<N, A> predExternal) {
		this.predExternal = predExternal;
	}

	public void setDistMap(Map<N, Integer> distExternal) {
		this.distExternal = distExternal;
	}
	
}
